class Trie
{
private:
    int count = 0;
    Trie *next[2] = {nullptr};

public:
    Trie()
    {
        count = 0;
        next[0] = next[1] = nullptr;
    }

    void insert(int x) // 在前缀树中插入值x
    {
        Trie *root = this;
        // 高位存储来Trie的前面，所以我们从左向右存储
        for (int i = 15; i >= 0; i--)
        {
            // 582910
            // 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 0 0 1 0 0 1 1 1 1 1 1 1 0
            int u = x >> i & 1;
            // 若第u位为空，则创建一个新节点，然后root移动到下一个节点
            if (!root->next[u])
                root->next[u] = new Trie();
            root = root->next[u];
            root->count++;
        }
    }

    // 找出比tar小的值
    int senexth(int x, int tar)
    {
        Trie *root = this;
        int res = 0;
        for (int i = 15; i >= 0 && root != nullptr; i--)
        {
            // 传进来的值对应的位
            int n = x >> i & 1;
            int t = tar >> i & 1;
            if (n == 0 && t == 0)
            {
                root = root->next[0];
            }
            else if (n == 0 && t == 1)
            {
                res += root->next[0] == NULL ? 0 : root->next[0]->count;
                root = root->next[1];
            }
            else if (n == 1 && t == 0)
            {
                root = root->next[1];
            }
            else if (n == 1 && t == 1)
            {
                res += root->next[1] == NULL ? 0 : root->next[1]->count;
                root = root->next[0];
            }
        }
        if (root)
        {
            res += root->count;
        }
        return res;
    }
};

class Solution
{
public:
    int countPairs(vector<int> &nums, int low, int high)
    {
        Trie *trie = new Trie();
        int ans = 0;
        for (auto &i : nums)
        {
            ans += trie->senexth(i, high) - trie->senexth(i, low - 1);
            trie->insert(i);
        }
        return ans;
    }
};
